package LeetCode;
import java.util.*;
public class LeetCodeMain3 {
//    List<List<String>> list=new ArrayList<>();
//    List<String> list1=new ArrayList<>();
//    public List<List<String>> partition(String s) {
//        backtracking(s,0);
//        return list;
//    }
//    public void backtracking(String s,int startIndex){
//        if (isPalindromicSubstring());
//    }
//    public boolean isPalindromicSubstring(String s){
//        char[] ch=s.toCharArray();
//        int start=0;
//        int end= ch.length-1;
//        while (start<=end){
//            if (ch[start]!=ch[end]){
//                return false;
//            }
//            start++;
//            end--;
//        }
//        return true;
//    }
//    List<List<Integer>> list=new ArrayList<>();
//    List<Integer> list1=new ArrayList<>();
//    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//        boolean arr[]=new boolean[candidates.length];
//        Arrays.fill(arr,false);
//        Arrays.sort(candidates);
//        backtracking(candidates,target,0,0,arr);
//        return list;
//    }
//    public void backtracking(int[] candidates,int target,int startIndex,int sum,boolean[] arr){
//            if (sum==target){
//                list.add(new ArrayList<Integer>(list1));
//                return;
//            }
//        for (int i = startIndex; i < candidates.length&&(sum+candidates[i])<=target; i++) {
//            if (i>0&&candidates[i]==candidates[i-1]&&arr[i-1]==false){
//                continue;
//            }
//            arr[i]=true;
//            list1.add(candidates[i]);
//            sum+=candidates[i];
//            backtracking(candidates,target,i+1,sum,arr);
//            arr[i]=false;
//            sum-=candidates[i];
//            list1.remove(list1.size()-1);
//    }
//    }
//    public static void main(String[] args) {
//        int[] candidates=new int[]{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
//        backtracking(candidates,30,0,0);
//        for (List<Integer> list2:list) {
//            for (int a:list2) {
//                System.out.println(a);
//            }
//        }
//    }
//        public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        backtracking1(candidates,target,0,0);
//        return list;
//    }
//    public void backtracking1(int[] candidates,int target,int startIndex,int sum){
//        if (sum>=target){
//            if (sum==target){
//                list.add(new ArrayList<Integer>(list1));
//                return;
//            }
//
//        }
//        for (int i = startIndex; i < candidates.length; i++) {
//            list1.add(candidates[i]);
//            sum+=candidates[i];
//            backtracking(candidates,target,i,sum);
//            sum-=candidates[i];
//            list1.remove(list1.size()-1);
//        }
//    }
}
